package DFS递归搜索与回溯.数独;

/**
 * @Date 2024/9/15 21:36
 * @description: 解数独
 * .    https://leetcode.cn/problems/sudoku-solver/description/
 * @Author LittleNight
 */
public class likou37 {


    /**
     * 解数独. 练习
     * @param board
     */
    boolean[][] row, col;
    boolean[][][] grid;
    public void solveSudoku(char[][] board) {
        // 初始化
        row = new boolean[9][10];
        col = new boolean[9][10];
        grid = new boolean[3][3][10];
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if(board[i][j] != '.') {
                    // 是数字, 标记为true, 表示已经出现过
                    int num = board[i][j] - '0';
                    row[i][num] = col[j][num] = grid[i / 3][j / 3][num] = true;
                }
            }
        }
        // 只需要一个原始数组. 需要返回值. 判断下一层是不是有结果
        dfs(board);
        return;
    }
    private boolean dfs(char[][] board) {
        // 出口已经蕴含在 for 循环中了. 就是循环9次
        // 主逻辑. 遍历原数组, 填表
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if(board[i][j] == '.') {
                    // 填表, 剪枝. 注意填表是 1-9 不是0-8
                    // for (int k = 0; k < 9; k++) {
                    for (int k = 1; k <= 9; k++) {
                        int num = k;
                        if (!row[i][num] && !col[j][num] && !grid[i / 3][j / 3][num]) {
                            // 都是 false, 表示没有出现过, 进行填表
                            board[i][j] = (char) (num + '0');
                            row[i][num] = col[j][num] = grid[i / 3][j / 3][num] = true;
                            // dfs(board); // 进入下一层
                            if (dfs(board)) return true; // 进入下一层
                            // 下一层不行, 进行回溯, 恢复现场
                            board[i][j] = '.';
                            row[i][num] = col[j][num] = grid[i / 3][j / 3][num] = false;
                        }
                    }
                    // 1-9 都不能填, 直接返回false给上一层
                    return false;
                }
            }
        }
        // 两层for 循环走完, 既不返回 true, 也不返回 false, 说明填满了
        return true;
    }


//    boolean[][] row; // 用于判断这个数在这一行有没有出现过
//    boolean[][] col;
//    boolean[][][] grid; // 用于判断这个数在小的九宫格内有没有出现过
//    public void solveSudoku(char[][] board) {
//        row = new boolean[9][10]; // 列给10个空间表示 0-9,不用映射2-1 3-2了
//        col = new boolean[9][10];
//        grid = new boolean[9][9][10];
//
//        // 先把标记数组填一下
//        for (int i = 0; i < 9; i++) {
//            for (int j = 0; j < 9; j++) {
//                if(board[i][j] != '.') {
//                    int num = board[i][j] - '0';
//                    row[i][num] = col[j][num] = grid[i / 3][j / 3][num] = true; // 标记已经出现过
//                }
//            }
//        }
//        dfs(board); // 进行dfs
//    }
//
//    public boolean dfs(char[][] board) {
//        for (int i = 0; i < 9; i++) {
//            for (int j = 0; j < 9; j++) {
//                if(board[i][j] == '.') {
//                    // 填数字
//                    for (int k = 1; k <= 9; k++) {
//                        // 剪枝. 都为 false 才可以填
//                        if(!row[i][k] && !col[j][k] && !grid[i / 3][j / 3][k]) {
//                            board[i][j] = (char)(k + '0');
//                            row[i][k] = col[j][k] = grid[i / 3][j / 3][k] = true; // 标记已经出现过
//                            if(dfs(board) == true) {
//                                return true;
//                            }
//                            // 失败, 进行回溯 恢复现场
//                            board[i][j] = '.';
//                            row[i][k] = col[j][k] = grid[i / 3][j / 3][k] = false;
//                        }
//                    }
//                    // 这个for循环没有返回 true, 说明 1-9都不可以
//                    return false;
//                }
//            }
//        }
//        // 两层 for 循环, 既没返回true又没返回false. 说明已经没有点了'.' 填满了.直接返回true
//        return true;
//    }
}
